package class51To60;

import java.io.*;

// https://www.luogu.com.cn/problem/P1886
public class  MostLessOrLargeQueue {

    public static int MAX_N = 1000005;

    public static int[] arr = new int[MAX_N];

    public static int n, k;

    public static int[] dequeue = new int[MAX_N];

    public static int h, t;

    public static int[] ans = new int[MAX_N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            k = (int) in.nval;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            minSlidingWindow();
            for (int i = 0; i < n - k + 1; i++) {
                out.print(ans[i] + " ");
            }
            out.println();
            maxSlidingWindow();
            for (int i = 0; i < n - k + 1; i++) {
                out.print(ans[i] + " ");
            }
        }
        out.flush();
        out.close();
        br.close();
    }

    private static void minSlidingWindow() {
        h = t = 0;
        for (int i = 0; i < k - 1; i++) {
            while (h < t && arr[i] <= arr[dequeue[t - 1]]) {
                t--;
            }
            dequeue[t++] = i;
        }
        int m = n - k + 1;
        for (int l = 0, r = k - 1; l < m; l++, r++) {
            while (h < t && arr[r] <= arr[dequeue[t - 1]]) {
                t--;
            }
            dequeue[t++] = r;
            ans[l] = arr[dequeue[h]];
            if (l == dequeue[h]) {
                h++;
            }
        }
    }

    public static void maxSlidingWindow() {
        h = t = 0;
        for (int i = 0; i < k - 1; i++) {
            while (h < t && arr[i] >= arr[dequeue[t - 1]]) {
                t--;
            }
            dequeue[t++] = i;
        }
        int m = n - k + 1;
        for (int l = 0, r = k - 1; l < m; l++, r++) {
            while (h < t && arr[r] >= arr[dequeue[t - 1]]) {
                t--;
            }
            dequeue[t++] = r;
            ans[l] = arr[dequeue[h]];
            if (l == dequeue[h]) {
                h++;
            }
        }
    }
}
